1. Field of the Invention
This invention relates to a method of operating a packet switched data communications network.
The method provides the means by which packet data can be routed through a switched packet network at speeds several orders of magnitude higher than is possible with current technology. This method enables the implementation of high speed wide area networks capable of transmitting voice, video and data on a single network. The method reduces significantly the complexity of managing the routing of packets through a switched network.
The method is primarily applicable to large (national and international) telecommunications networks and to large private networks.
2. Description of the Prior Art
From the perspective of switching technology, there are currently three major classes of network:
Firstly, there are switched point-to-point networks, typified by the world's Public Switched Telephone Networks (PSTNs). Ignoring the residual analog subsets, these networks consist of digital point-to-point links connecting digital switching nodes (switches) and end users together.
The PSTNs are characterized by the way in which they connect end users by setting up a dedicated path through the network for the duration of a connection, by their transmission of continuous unstructured bit streams, and by the relatively low bandwidth of each connection, 64 kb/s. Permanent (dedicated) circuits can be provided by wiring a permanent path through the network, and multiple parallel permanent circuits can be used to provide higher bandwidth.
These networks provide fast transmission, with minimal switching delays. On the other hand, they make poor use of the available bandwidth, as a physical circuit is dedicated to each conversation and spare capacity in the circuit cannot be re-allocated to other users. As an example, in a typical telephone conversation only one person is speaking at any time, so at least half the capacity is unused at such times. Couple this with the fact that present technology can compress the conversation into a bit stream of less than 32 kb/s without any loss of quality, and it will become apparent that the PSTNs are very wasteful of the available capacity.
The switched point-to-point networks provide no error detection or correction capabilities, as the occasional bit error has no effect on voice transmissions.
Finally, while the PSTNs can carry voice with capacity to spare, their fixed link speed of 64 kb/s makes them unusable for signals such as video that require much higher capacity circuits.
Secondly, there are packet switching networks. Like the PSTNs, these are usually wide area networks (and usually piggy-back on top of a PSTN using dedicated circuits to connect the packet switches). The topology of a packet switched network is similar to that of a switched point to point network. The distinction is made by the traffic and switching technique. Rather than carrying raw continuous bit streams, these networks carry packets and the switching nodes route data on a packet by packet basis. This technique permits traffic to share the physical path(s) between nodes, and is well suited the bursty traffic that is typical of computer systems.
Packet switching systems provide `virtual circuits`. A path through the system is set up for a call, but no capacity is reserved. Many virtual circuits can therefore share physical links in the network. When a packet is received at a switching node, it is read by the processor at each node and routed based on a virtual circuit id. contained in the packet header.
Packet switching technology provides for the detection and correction of errors in the data. This is necessary for most computer applications, but is not needed for voice and data systems, where the occasional bit error has no discernible affect on the received signal.
The packet switch networks are (theoretically, at least) capable of carrying much higher speed traffic. However, they suffer from relatively long and unpredictable end-to-end transmission times (in the order of hundreds of milliseconds for older technologies such as X.25). While they are adequate for computer traffic, these switching delays make them unusable for voice and video.
Finally, there are the bus networks. These are typically local area networks using a single bus or loop that carries packet data at high speed (10 Mb/s to 100 Mb/s or more), to which a number of computers are attached. There is no switching as such. All the computer systems transmit on the bus, listen to the bus, and extract the packets addressed to themselves. Larger systems are made up of multiple networks connected by various types of bridges and routers, but none of these systems is capable of expansion to a wide area network with the scope and connections of a PSTN. Like the wide area packet networks, these systems suffer from switching induced transmission delays when multiple networks are involved.
The data transmitted among computers is typified by bursts of data with intervening periods without data. Such systems therefore do not make effective use of point-to-point switched networks.
Almost all computer applications require error-free transmission, which means that the detection of errors and re-transmission of data are mandatory.
On the other hand, most applications can tolerate significant delays in the delivery of data and can tolerate significant variation in transmission delays.
In contrast to computer data, digitized voice and video communications systems typically have opposite requirements. They generate a continuous stream of data which must be delivered quickly and regularly. When packetized, transmission delays must not vary by more than a few milliseconds. Data which is not delivered on time is useless and must be discarded.
On the other hand, voice and video systems can tolerate some errors, since the occasional dropped bit does not have any significant effect on the resulting voice or video quality.
Video signals, in particular, require a high bandwidth. Whereas 64 kilobits is adequate for uncompressed `telephony standard` voice transmission, TV quality video requires bandwidths of the order of megabits per second, even for a radically compressed signal.
Voice and video are traditionally carried on dedicated circuits using circuit switching (as in the PSTN).
The challenge, for the last several years, has been to devise data communications systems that can accommodate both types of data on a single network in order to accommodate the hybrid applications which are now being developed or planned.
Several attempts have been made recently to design such a hybrid network. The Frame Relay, ATM, DQDB, and SONET technologies all provide improvements over the traditional networks in some aspects of the problem, without quite solving all the problems in a true hybrid network.
The frame format used by Frame Relay is a derivative of the ISDN LAP-D framing structure. Like older packet protocols, frame relay uses an address field which identifies a virtual circuit. This has two implications for frame (packet) switching:
It is necessary to set up and tear down a virtual circuit through the network in order to transmit data. This is merely an initialization and termination overhead, although it can be significant for short transactions.
At each switch in the packet's path, the packet must be read by the switch processor and the virtual circuit id decoded in order to determine the appropriate outward path from the switch. The decoding of the virtual circuit id at each switch means is a processor intensive operation and a prime source of switching delay.
Basic frame relay is limited to 1024 circuits, which limits its use to private networks. Various extensions permit up to 22 bits of address field, or 4 million simultaneous circuits--still small by PSTN standards. This limited addressing capability simplifies the switching algorithm and reduces the switching overhead. Larger networks can be implemented by internetworking several frame relay networks.
Frame relay also gains speed, relative to the older (X.25, etc.) technologies by not performing error detection and correction in each switching node and by not guaranteeing sequencing or delivery of packets. Given the reliability of current technology, dropping error detection and correction from the switching nodes provides a significant speed improvement with minimal cost. Similarly, relegating the re-sequencing of packets to the customer premises equipment improves switching speed in the network at a relatively low cost.
The most controversial way in which frame relay gains speed is to discard packets when network congestion occurs. While this can be beneficial to many real-time applications, it can be a source of severe delays in session-oriented traffic.
The major remaining delay in switching frame relay packets is the delay involved in absorbing the packet into the switch and performing the routing algorithm.
Frame relay switching speed is estimated to be approximately 5 to 10 milliseconds per node.
Of all existing technologies, ATM comes nearest to being able to handle voice, video, and data. Like frame relay, it depends upon switched virtual circuit connections.
Like frame relay, ATM provides virtual circuits between customer end points, and does not perform error detection and correction in each switching node or guarantee sequencing or delivery of packets.
ATM networks transmit packets of fixed length (53 bytes) called `cells`. Unlike frame relay, the virtual circuit identifiers are local to each link in the network and can be changed at each switch. While this resolves the frame relay problem of limited address capability, it does so at the cost of greater complexity in each switching node.
ATM switching speed is currently of the same order of magnitude as frame relay. Work in progress on photonic switching technologies will provide much faster switching. However, the implementation of the switching technique in hardware is made more complex by several orders of magnitude by the ATM protocol, and there are significant problems in implementing the ATM virtual paths and channels in a network of significant size.
DQDB is, in essence, an extension of the LAN token ring technology to a metropolitan area. It is specified to run at 45 Mbit/s, 155 Mbit/s, or 622 Mbit/s. It is a dual bus technology and, as such, is severely limited in the number of connections it can handle. DQDB is primarily designed for high speed computer--computer communications. It is designed to transmit short (53 byte) packets at high speed, and the sending and receiving stations are responsible for splitting larger packets at the transmitter and reconstituting them at the receiver.
Given the limited access to DQDB systems, they are not suited for wide area networks, though they can operate as a metropolitan backbone link in a larger internetworking system, or multiple DQDB systems can be internetworked to provide a much larger network. In these cases, however, the queuing, switching, and assembly/disassembly of packets incurs significant delays.
Typical delays for a DS3 network is estimated at about 20 ms.
SONET is a fibber optic multiplexed transmission standard being developed by the CCITT. As a transmission and multiplexing technology, it supports various end-to-end transmission technologies, such as frame relay, ISDN, and FDDI. It does not, per se, provide any switching capability.
Like DQDB, FDDI is an extension of the token ring technology to higher speeds and to metropolitan areas. In the case of FDDI, the transmission speed is 100 Mbits/sec and an FDDI network permits up to 500 connections and a maximum loop length of 200 km. All the comments on DQDB are applicable to FDDI.
For the purposes of this specification, networks will be divided into two types: those which are large enough to require routing of data through intermediate nodes, and those which are not. The latter type is typically the isolated LAN, consisting of a single bus or star topology with no external connections. The switching networks range from linked LANs all the way up to the public switched telephone networks (PSTNs).
It is the larger networks with which the present invention is concerned. Addressing schemes for the PSTNs use the familiar telephone numbers--accepted (perhaps because there is no alternative), but by no means ideal. Data network naming schemes generally use a similar scheme of non-meaningful numeric or alphanumeric strings. The Internet is one of the few networks to use a more human-friendly naming scheme.